package algorithm;

import structure.*;

import java.util.ArrayList;

import structure.enumerateGrammar;
import structure.grammar;

public class algorithm {

	public algorithm(){
		
	}
	
	//esegue la First1 della produzione
	//in caso di left recursion evitare di processare simboli gia processati
	public static ArrayList<String> First1(enumerateGrammar e, String beta, 
									ArrayList<String> toReturn,
									ArrayList<String> alreadyChecked){
		//controlli su consistenza
		if(toReturn == null) 
			toReturn= new ArrayList<String>();
		
		if(alreadyChecked == null)
			alreadyChecked= new ArrayList<String>();
		//-------------------------------------
		
		ArrayList<String> nullable= e.getNullable();
		if(nullable == null) nullable= new ArrayList<String>();
		
		if(!e.contains(beta)){
			System.out.println("ERROR[Function: First1]: il beta (" + beta +")  passato non è presente nella grammatica!");
			return null;
		}
		//First1(x)
		else if(beta.equals("")){
			toReturn.add("");
			return toReturn;
		}
		//First1(x)- {e} U First(alpha)
		else if(beta.length() == 1 && nullable.contains(beta)){
			ArrayList<Integer> index= e.getLeftsidePosition(beta);
			
			if(index != null){
				
				for(int i : index){
					//prendo il rightside della produzione
					String rightside= e.getRightside().get(i);

					String first= rightside.substring(0, 1);
						
					if(Character.isUpperCase(first.charAt(0))){
						//se è un non terminale potremmo incappare in ricorsione infinita
						//controllo che non abbia gia controllato il non terminale in questione
						if(!alreadyChecked.contains(first)){
							
							alreadyChecked.add(first);
							First1(e, first, toReturn, alreadyChecked);
						}
						
					}
					else if(!Character.isUpperCase(first.charAt(0))){ 
		
						if(!toReturn.contains(first))
							toReturn.add(first);
					}
				}
			}
			int toRemove=-1;
			for(int k=0; k<toReturn.size(); k++){
				
				if(toReturn.get(k).equals("e")){
					toRemove= k;
					break;
				}
			}
			
			if(toRemove >= 0)
				toReturn.remove(toRemove);
			
			if(beta.length() > 1){
				ArrayList<String> firstAlpha= First1(e, beta.substring(1), null, null);
			
				toReturn.addAll(firstAlpha);
			}
			
			return toReturn;
		}
		else if(beta.length() == 1 && !nullable.contains(beta)){

			if(e.getVN().contains(beta)){
				ArrayList<Integer> index= e.getLeftsidePosition(beta);
				
				if(index != null){
					
					for(int i : index){
						//prendo il rightside della produzione
						String rightside= e.getRightside().get(i);

						String first= rightside.substring(0, 1);
							
						if(Character.isUpperCase(first.charAt(0))){
							//se è un non terminale potremmo incappare in ricorsione infinita
							//controllo che non abbia gia controllato il non terminale in questione
							if(!alreadyChecked.contains(first)){
								
								alreadyChecked.add(first);
								First1(e, first, toReturn, alreadyChecked);
							}
							
						}
						else if(!Character.isUpperCase(first.charAt(0))){ 
			
							if(!toReturn.contains(first))
								toReturn.add(first);
						}
					}
				}
			}
			else
				
				toReturn.add(beta);
			return toReturn;
		}
		else{
			
			beta= beta.substring(0, 1);
			toReturn.addAll(First1(e, beta, null, null));
			return toReturn;
		}
		
			
	}

	
	/*
	 * Elimina i simboli che non generano word
	 * Data una grammatica ne genera una equivalente dove VN' include solo i simboli appartenenti a VT*
	 * e P' include solo le produzioni i cui simboli appartengono a VT U VN'
	 */
	public static grammar FromBelowProcedure(grammar g){
		
		ArrayList<production> productions= g.getAllProduction();
		ArrayList<String> vn= new ArrayList<String>();
		ArrayList<String> union= new ArrayList<String>();
		
		for(production p : productions){
			
			vn.add(p.getLeftSide());
		}
		
		union.addAll(g.getVT());
		union.addAll(vn);
		
		System.out.println("union= " + union);
		for(production p : productions){
			ArrayList<String> tmp= new ArrayList<String>();

			for(int j=0; j<p.getRightSide().size(); j++){
				
				String right= p.getRightSide().get(j);
				boolean there= false;
				for(int k=0; k<right.length(); k++){
					
					String tmpS= right.substring(k, k+1);
					if(!union.contains(tmpS)){
						there= true;
					}
					
				}
				if(!there && !tmp.contains(right)) tmp.add(right);
			}
			p.setRightSide(tmp);
		}
		
		
		g.setVN(vn);
		g.setP(productions);
		return g;
	}
	
	//Elimina i simboli che non sono raggiungibili dal simbolo iniziale
	public static grammar FromAboveProcedure(grammar g){

		ArrayList<String> vt= new ArrayList<String>();
		ArrayList<String> vn= new ArrayList<String>();
		vn.add(g.getS());
		
		for(production p : g.getAllProduction()){
			
			if(vn.contains(p.getLeftSide())){
				for(int k=0; k<p.getRightSide().size(); k++){
					
					String right= p.getRightSide().get(k);
					for(int j=0; j<right.length(); j++){
						
						String tmpS= right.substring(j, j+1);
						if(Character.isUpperCase(tmpS.charAt(0)))
							vn.add(tmpS);
						else
							vt.add(tmpS);
					}
				}
			}
		}
		
		for(production p : g.getAllProduction()){
			
			ArrayList<String> tmpP= new ArrayList<String>();
			if(vn.contains(p.getLeftSide())){
				tmpP.addAll(p.getRightSide());
			}
			p.setRightSide(tmpP);
		}
		
		ArrayList<production> tmp= new ArrayList<production>();
		for(production p : g.getAllProduction()){
			
			if(!p.getRightSide().isEmpty()){
				tmp.add(p);
			}
		}
		g.setP(tmp);
		
		return g;
	}
}
